int initCounter = 1;

void remove_nvg_lhs(struct BB *bb, int lhs)
{
	if (bb->nvg == NULL) return;
	struct NVG *temp = bb->nvg;
	if (temp->lhs == lhs) {
		bb->nvg = temp->next;
		free(temp);
	} else {
		while (temp->next != NULL) {
			if (temp->next->lhs == lhs) {
				struct NVG *next = temp->next;
				temp->next = next->next;
				free(next);
			} else {
				temp = temp->next;
			}
		}
	}
}

void nvg_evaluate_while_node(struct BB *bb, struct Three_AddressNode *node)
{
	struct nvgOperand *lhsOp = check_lhs_nvg(bb, node->LHS);
	if (lhsOp != NULL) {
		// The LHS already exists in the nvg and thus cannot be used for nvg evaluating of this block - remove it
		remove_nvg_lhs(bb, node->LHS);
	}
}

void nvg_evaluate_while_block(struct BB *bb)
{
	struct Three_AddressNode *temp = bb->entry;
	while (temp != NULL) {
		nvg_evaluate_while_node(bb, temp);
		temp = temp->next;
	}
}


void nvg_evaluate_block(struct BB *bb) 
{
	struct Three_AddressNode *temp = bb->entry;
	nvg_evaluate_node(temp, bb);
	bb->marked = 1;
	if (temp->delFlag == 1) 
	{
		// Entry point treated differently than the rest of the nodes - if the entry is set for deletion, delete it and re-call the evaluation
		bb->entry = temp->next;
		remove_from_node_list(temp);
		free(temp);
		nvg_evaluate_block(bb);
	}
	else {
		// Otherwise, proceed with evaluating the rest of the nodes in the block
		while (temp->next != NULL)
		{
			//printf("\nEVALUATING***********************\n");
			//print_three_address(temp->next);
			//printf("\n*********************************\n");
			struct Three_AddressNode *next = temp->next;
			nvg_evaluate_node(next, bb);
			if (next->delFlag == 1)
			{
				//printf("\nTHIS IS BEING DELETED NVG***********************\n");
				//print_three_address(next);
				//printf("\n******************************************\n");
				temp->next = next->next;
                                if (temp->next == NULL) {
                                        temp->ptr1 = next->ptr1;
                                        temp->ptr2 = next->ptr2;
                                }
				remove_from_node_list(next);
				free(next);
			} else {
				temp = temp->next;
			}
			//printf("\nNEXT UP:\n");
			//if (temp->next != NULL) print_three_address(temp->next);
			//printf("*****************************************\n");
		}
	}
}

int get_next_init_key()
{
	char *name = (char *)(malloc(32*sizeof(char)));
	strcpy(name, "init.");
	strcat(name, inttostring(initCounter));
	initCounter++;
	return makekey(name, MAX_VARIABLES);
}

struct nvgOperand *getOperand(int operand, struct BB *bb, struct Three_AddressNode *node)
{
	struct nvgOperand *newOperand = (struct nvgOperand *)(malloc(sizeof(struct nvgOperand)));
	newOperand->isConst = 0;
	struct NVG *op = check_lhs_nvg(bb, operand);
	if (op == NULL)
	{
		// The operand is not in the nvg table, so see what type it is in the symbol table
		struct cfg_symtab_elem *var = cfg_symtab_lookup(operand);
		if (var->type == SYM_TYPE_USER) 
		{
			// The variable is user-defined, so add it to the nvg table with next unique init value
			int init_key = get_next_init_key();
			add_to_nvg(operand, init_key, 0, bb);
			newOperand->opValue = init_key;
		}
		else if (var->type == SYM_TYPE_TEMP)
		{
			// This is a temporary variable, so check if it needs to be replaced first
			struct replaceTable *replace = lookupReplacement(bb, operand);
			if (replace != NULL)
			{
				// A replacement is available for the variable - replace the variable and delete the replacement, it is no longer needed
				int toDel = operand;
				operand = replace->replace;
				remove_replacement(bb, toDel);
				op = check_lhs_nvg(bb, operand);
				if (op == NULL)
				{
					// We are dealing with a constant
					struct cfg_symtab_elem *constVar = cfg_symtab_lookup(operand);
					newOperand->isConst = 1;
					newOperand->opConst = atoi(constVar->val);
					newOperand->opValue = operand;
				}
				else 
				{
					// We are dealing with a variable
					newOperand->opValue = op->rhs;
				}
				if (node->operand1 == toDel) node->operand1 = operand;
				else if (node->operand2 == toDel) node->operand2 = operand;
			}
			// Should be impossible to get an else in this case - either the temporary variable has been declared or it needs to be replaced
		}
		else if (var->type == SYM_TYPE_CONST)
		{
			// This is a constant number, so save the constant as an integer and the operand value as a key for the constant
			newOperand->isConst = 1;
			newOperand->opConst = atoi(var->val);
			newOperand->opValue = getConstKey(newOperand->opConst);
		}
	}
	else 
	{
		if (op->constant == 1)
		{
			// The value of the variable is a constant
			newOperand->isConst = 1;
			newOperand->opConst = op->rhs;
			newOperand->opValue = getConstKey(op->rhs);

			// We want to replace the variable with a constant if it is a constant
			if (node->operand1 == operand) 
			{
				node->operand1 = newOperand->opValue;
			}
			else if (node->operand2 == operand) 
			{
				node->operand2 = newOperand->opValue;
			}
		}
		else 
		{
			// The value is not a constant, so just keep it as the value
			newOperand->opValue = op->rhs;
		}
	}
	return newOperand;

}

int evaluate_const_operation(int const1, int const2, int operator)
{
	if (operator == PLUS) return const1 + const2;
	else if (operator == MINUS) return const1 - const2;
	else if (operator == STAR) return const1 * const2;
	else if (operator == SLASH) {
		if (const2 == 0) return 0; 
		else return const1 / const2;
	}
	else if (operator == MOD) return const1 % const2;
	else return NULL;
}

int evaluate_non_const_operation(int val1, int val2, int operator)
{
	char *name = (char *)(malloc(32*sizeof(char)));
	// Check to see what operation is taking place - will determine if commutative operations need to be considered
	if (operator == PLUS || operator == STAR)
	{
		// Order the opValues before doing the hash to keep the commutative property in tact
		if (val1 > val2) 
		{
			strcpy(name, inttostring(val2));
			strcat(name, inttostring(convert_operator(operator)));
			strcat(name, inttostring(val1));
		} else {
			strcpy(name, inttostring(val1));
			strcat(name, inttostring(convert_operator(operator)));
			strcat(name, inttostring(val2));
		}
	} else {
		// The order matters with the rest of the math operations
		strcpy(name, inttostring(val1));
		strcat(name, inttostring(convert_operator(operator)));
		strcat(name, inttostring(val2));
	}
	return makekey(name, MAX_VARIABLES);
}

struct nvgOperand *nvg_evaluate_two_operands(struct nvgOperand *op1, struct nvgOperand *op2, struct Three_AddressNode *node)
{
	if (op1->isConst == 1 && op2->isConst == 1)
	{	
		// Both operands are constants, so just perform the required operation on them
		struct nvgOperand *rhs = (struct nvgOperand *)(malloc(sizeof(struct nvgOperand)));
		rhs->isConst = 1;
		rhs->opConst = evaluate_const_operation(op1->opConst, op2->opConst, node->operator);
		rhs->opValue = rhs->opConst;
		return rhs;
	} else {
		// One of the operands is not a constant
		// Check the arithmetic rules
		struct nvgOperand *rhs = evaluate_arithmetic(op1, op2, node);

		// See if any of the arithmetic rules applied
		if (rhs != NULL) return rhs;

		// No rules applied - just make the hash
		rhs = (struct nvgOperand *)(malloc(sizeof(struct nvgOperand)));
		rhs->isConst = 0;
		rhs->opValue = evaluate_non_const_operation(op1->opValue, op2->opValue, node->operator);
		return rhs;
	}
}

struct nvgOperand *nvg_evaluate_operand1(struct nvgOperand *op)
{
	// We are dealing with an assignment of the nature x = y
	struct nvgOperand *rhs = (struct nvgOperand *)(malloc(sizeof(struct nvgOperand)));
	rhs->isConst = op->isConst;
	rhs->opConst = op->opConst;
	rhs->opValue = op->opValue;
	return rhs;
}

struct nvgOperand *nvg_evaluate_operand2(struct nvgOperand *op, int operator)
{
	// We are dealing with an assignment of the nature x = -y
	struct nvgOperand *rhs = (struct nvgOperand *)(malloc(sizeof(struct nvgOperand)));
	if (op->isConst == 1)
	{
		rhs->isConst = 1;
		// Perform the desired operation on the constant
		if (operator == PLUS) rhs->opConst = op->opConst;
		else if (operator == MINUS) rhs->opConst = -op->opConst;
		rhs->opValue = rhs->opConst;
	} else {
		rhs->isConst = 0;
		char *name = (char *)(malloc(32*sizeof(char)));
		strcpy(name, inttostring(convert_operator(operator)));
		strcat(name, inttostring(op->opValue));
		rhs->opValue = makekey(name, MAX_VARIABLES);
	}
	return rhs;
}

struct nvgOperand *evaluate_arithmetic(struct nvgOperand *op1, struct nvgOperand *op2, struct Three_AddressNode *node)
{
	// Initialize variables for result
	int applied = 0;
	int rhsIsConst = 0;
	int rhsOpConst = 0;
	int rhsOpValue = 0;

	if (node->operator == PLUS) {
		// a + 0 = a
		if (op1->isConst == 1 && op1->opConst == 0) {
			applied = 1;
			rhsOpValue = op2->opValue;
		} else if (op2->isConst == 1 && op2->opConst == 0) {
			applied = 1;
			rhsOpValue = op1->opValue;
		}
	} else if (node->operator == MINUS) {
		// 0 - a = -a
		if (op1->isConst == 1 && op1->opConst == 0) {
			return nvg_evaluate_operand2(op2, MINUS);
		} else if (op2->isConst == 1 && op2->opConst == 0) {
			// a - 0 = a
			applied = 1;
			rhsOpValue = op1->opValue;
		} else if (op1->isConst == 0 && op2->isConst == 0 && node->operand1 == node->operand2) {
			// a - a = 0
			applied = 1;
			rhsIsConst = 1;
			rhsOpConst = 0;
			rhsOpValue = 0;
		}
	} else if (node->operator == STAR) {
		if ((op1->isConst == 1 && op1->opConst == 0) || (op2->isConst == 1 && op2->opConst == 0)) {
			// 0 * a = 0
			applied = 1;
			rhsIsConst = 1;
			rhsOpConst = 0;
			rhsOpValue = 0;
		} else if ((op1->isConst == 1 && op1->opConst == 2) || (op2->isConst == 1 && op2->opConst == 2)) {
			// 2 * a = a + a
			struct nvgOperand *nonConstOp;
			int nonConstInt;
			if (op1->isConst == 1) {
				nonConstOp = op2;
				nonConstInt = node->operand2;
			} else {
				nonConstOp = op1;
				nonConstInt = node->operand1;
			}

			// Modify node variables
			node->operand1 = nonConstInt;
			node->operand2 = nonConstInt;
			node->operator = PLUS;

			// Return the two operand evaluation
			return nvg_evaluate_two_operands(nonConstOp, nonConstOp, node);
		} else if ((op1->isConst == 1 && op1->opConst == 1) || (op2->isConst == 1 && op2->opConst == 1)) {
			// 1 * a = a
			if (op1->isConst == 1) {
				applied = 1;
				rhsOpValue = op2->opValue;
			} else {
				// a * 1 = a
				applied = 1;
				rhsOpValue = op1->opValue;
			}
		}
	} else if (node->operator == SLASH) {
		if (op2->isConst == 1 && op2->opConst == 1) {
			// a / 1 = a
			applied = 1;
			rhsOpValue = op1->opValue;
		} else if (op1->isConst == 0 && op2->isConst == 0 && node->operand1 == node->operand2) {
			// a / a = 1
			applied = 1;
			rhsIsConst = 1;
			rhsOpConst = 1;
			rhsOpValue = 1;
		}
	} else if (node->operator == MOD) {
		if (op1->isConst == 1 && op1->opConst == 1) {
			// 1 % a = 1
			applied = 1;
			rhsIsConst = 1;
			rhsOpConst = 1;
			rhsOpValue = 1;
		} else if (op2->isConst == 1 && op2->opConst == 1) {
			// a % 1 = 0
			applied = 1;
			rhsIsConst = 1;
			rhsOpConst = 0;
			rhsOpValue = 0;
		} else if (op1->isConst == 0 && op2->isConst == 0 && node->operand1 == node->operand2) {
			// a % a = 0
			applied = 1;
			rhsIsConst = 1;
			rhsOpConst = 0;
			rhsOpValue = 0;
		}
	}

	// If a rule has been applied, return a rhs with the computed values, return NULL if otherwise
	if (applied == 0) return NULL;
	struct nvgOperand *rhs = (struct nvgOperand *)(malloc(sizeof(struct nvgOperand)));
	rhs->isConst = rhsIsConst;
	rhs->opConst = rhsOpConst;
	rhs->opValue = rhsOpValue;
	return rhs;
}

	void nvg_evaluate_node(struct Three_AddressNode *node, struct BB *bb) {
		if (node->type == THREE_ADDRESS_IF)
		{
			struct replaceTable *replace = lookupReplacement(bb, node->LHS);
			if (replace != NULL) {
				node->LHS = replace->replace;
			}
		}
		else if (node->type == THREE_ADDRESS_ASSIGN)
		{
			// Check operand 1 in the nvg table
			struct nvgOperand *op1 = NULL;
			if (node->operand1 != NULL) op1 = getOperand(node->operand1, bb, node);
			struct nvgOperand *op2 = NULL;
			if (node->operand2 != NULL) op2 = getOperand(node->operand2, bb, node);	

			// Check to see if the LHS exists already in the NVG table, and store its rhs if so
			int defaultRHS = NULL;
			int defaultConst = 0;
			struct NVG *lhs = check_lhs_nvg(bb, node->LHS);
			if (lhs != NULL) {
				defaultRHS = lhs->rhs;
				defaultConst = lhs->constant;
			}
			struct nvgOperand *rhs;
			if (op1 != NULL && op2 != NULL) {
				rhs = nvg_evaluate_two_operands(op1, op2, node);
			}
			else if (op1 != NULL) 
			{
				rhs = nvg_evaluate_operand1(op1);
			}
			else 
			{
				// There should be at least one operand defined
				rhs = nvg_evaluate_operand2(op2, node->operator);
			}

			// Check to see if the operation changed the value of the variable - if not, it is a redundant call and can be deleted
			if (defaultRHS != NULL)
			{
				if ((defaultConst == 0 && rhs->isConst == 0 && defaultRHS == rhs->opValue) || (defaultConst == 1 && rhs->isConst == 1 && defaultRHS == rhs->opConst))
				{
					node->delFlag = 1;
					return;
				}
			}

			if (lhs == NULL)
			{
				// The LHS variable has not been initialized yet in the NVG table. Find out what type it is first
				struct cfg_symtab_elem *lhsVar = cfg_symtab_lookup(node->LHS);

				if (lhsVar->type == SYM_TYPE_USER)
				{
					// The user created this variable, so add it to the nvg regardless of if it is a duplicate
					if (rhs->isConst == 1) add_to_nvg(node->LHS, rhs->opConst, rhs->isConst, bb);
					else add_to_nvg(node->LHS, rhs->opValue, rhs->isConst, bb);
				} else {
					// Otherwise it has to be a temporary variable. First check to see if the value is equivalent to another in the nvg table
					struct NVG *existingRHS = check_rhs_nvg(bb, rhs->opValue);
					if (existingRHS != NULL)
					{
						// Another variable has that value already - have this temporary variable replaced
						add_to_replace(bb, node->LHS, existingRHS->lhs);
						node->delFlag = 1;
					} else {
						// No other variable has that value - however, is it a constant?
						if (rhs->isConst == 1)
						{
							// It is a constant - thus the temporary variable can be removed
							// First, does the constant already exist in the symbol table?
							int key = getConstKey(rhs->opConst);
							struct cfg_symtab_elem *lhsVar = cfg_symtab_lookup(key);
							if (lhsVar == NULL)
							{
								// No it doesn't - so add it
								char *symName = inttostring(rhs->opConst);
								cfg_symtab_add(SYM_TYPE_CONST, key, symName);
							}
							// Add to the replacement table the key of the constant to be replaced
							add_to_replace(bb, node->LHS, key);
							node->delFlag = 1;
						}
						else {
							// It is not a constant - so add it to the nvg table
							add_to_nvg(node->LHS, rhs->opValue, rhs->isConst, bb);
						}
					}
				}
			} else {
				// The LHS variable has already been initialized. Update the values
				lhs->constant = rhs->isConst;
				if (rhs->isConst == 1)
					lhs->rhs = rhs->opConst;
				else
					lhs->rhs = rhs->opValue;
			}
		}

		//print_nvg(bb);
		return;
	}


struct NVG * nvg_init()
{
	struct NVG * new = (struct NVG *)(malloc(sizeof(struct NVG)));
	new->next = NULL;

	return new;
}

struct NVG *check_rhs_nvg (struct BB *bb, int rhs) 
{
	struct NVG *temp = bb->nvg;
	while (temp != NULL)
	{
		// We are only looking for keys, not constants, so even if the rhs == rhs, if it's a constant it doesn't count
		if (temp->rhs == rhs && temp->constant == 0)
		{
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}

struct NVG *check_lhs_nvg (struct BB *bb, int lhs) 
{
	struct NVG *temp = bb->nvg;
	while (temp != NULL) 
	{
		if (temp->lhs == lhs)
		{
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}

void nvg_init_with_parent (struct BB *bb)
{
	struct NVG * parent1, * parent2;
	if (bb->parentCount == 1)
	{
		parent1 = bb->parents->parent->nvg;
		while (parent1 != NULL)
		{
			add_to_nvg (parent1->lhs, parent1->rhs, parent1->constant, bb);
			parent1 = parent1->next;
		}
	}
	else if (bb->parentCount == 2)
	{
		//printf("***** bb num %d, parent1 %d , parent2 %d ****** \n", bb->number, bb->parents->parent->number, bb->parents->nextparent->parent->number); 
		parent1 = bb->parents->parent->nvg;
		while (parent1 != NULL)
		{
			parent2 = bb->parents->nextparent->parent->nvg;
			while (parent2 != NULL)
			{
				//                                      printf("%d-%d, %d-%d \n", parent1->lhs, parent1->rhs,parent2->lhs, parent2->rhs);
				if (((parent1->lhs) && (parent1->lhs==parent2->lhs)) && (parent1->rhs==parent2->rhs))
				{
					add_to_nvg (parent2->lhs, parent2->rhs, parent2->constant, bb);
				}
				parent2 = parent2->next;
			}
			parent1 = parent1->next;
		} 
	}
	return;
}

void add_to_nvg (int lhs, int rhs, int constant, struct BB *bb)
{
	struct NVG * newNode = nvg_init ();
	newNode->lhs = lhs;
	newNode->rhs = rhs;
	newNode->constant = constant;

	struct NVG * node = bb->nvg;
	if (node == NULL)
	{
		bb->nvg = newNode;
	}
	else {
		while (node->next != NULL)
		{
			node = node->next;
		}
		node->next = newNode;
	}
}


void print_nvg (struct BB *bb)
{
	printf("\n\n\n======NVG===== %d\n", bb->number);
	struct NVG *temp = bb->nvg;
	while (temp != NULL)
	{
		printf("Constant: %d \t\t LHS: %d \t\t RHS: %d \t\t Label: %s\n", temp->constant, temp->lhs, temp->rhs, cfg_symtab_get_val(temp->lhs));
		temp = temp->next;
	}
	printf("=======================\n\n");

	printf("====REPLACEMENTS====\n");
	struct replaceTable *rep = bb->replace;
	while (rep != NULL)
	{
		printf("Del: %s \t\t Replace: %s\n", cfg_symtab_get_val(rep->del), cfg_symtab_get_val(rep->replace));
		rep = rep->next;
	}	
	printf("====================\n");
}

struct BB * nvg_evaluate_blocks(struct BB* bb, int force, int extended)
{
	struct Three_AddressNode *exitNodeOfBlock = bb->exit;
	struct BB * dummy1 = NULL;
	struct BB * dummy2 = NULL;

	/* if current block is pointing to dummy, then return */
	// If force is passed, then we have printed all of the parents of the dummy and can now print the dummy itself
	if ((bb->parentCount > 1 || bb->marked == 1) && force == 0) 
	{
		// Having a marked block in this case means we are visiting the while loop conditional block
		if (bb->marked == 1) return NULL;
		return bb;
	}

	/* initialize nvg with parent */
        if (extended == 1)
	    nvg_init_with_parent (bb);

	// We do not want to evaluate the while condition block
	if (bb->type != BB_TYPE_WHILE_COND) {
		// While bodies have special rules - cleanup the nvg table before and after the block is evaluated
		if (bb->type == BB_TYPE_WHILE_BODY) {
			nvg_evaluate_while_block(bb);
		}

		/* evaluate the current block */
		nvg_evaluate_block(bb);

		if (bb->type == BB_TYPE_WHILE_BODY) {
			nvg_evaluate_while_block(bb);
		}
	}

	/* recursive call to evaluate next block */
	if (exitNodeOfBlock->ptr1!=NULL)
		dummy1 = nvg_evaluate_blocks(exitNodeOfBlock->ptr1, 0, extended);

	if (exitNodeOfBlock->ptr2!=NULL)
		dummy2 = nvg_evaluate_blocks(exitNodeOfBlock->ptr2, 0, extended);

	/* check if they are pointing to dummies */
	if (dummy1 != NULL && dummy2 != NULL)
	{
		return nvg_evaluate_blocks (dummy2, 1, extended);
	}
	else if (dummy1 != NULL) return dummy1;
	else if (dummy2 != NULL) return dummy2;

	return NULL;      
}

void value_numbering (struct CFG * c, int extended)
{
	if (c->entry == NULL) return;
	struct BB* curBB = c->entry;
	nvg_evaluate_blocks(curBB, 1, extended);
}

